This is a non-randomized study to estimate the frequency of eradication of MAC in previously MAC-infected individuals with a adequate response to antiretroviral therapy. Subjects must be diagnosed with MAC, be treated with a macrolide-based regimen for one year, have CD4 counts >100 cells/mm3, and currently be receiving antiretroviral therapy for at least 16 weeks. The primary objective is to determine if anti-mycobacterial therapy can be withdrawn from these subjects and to estimate the duration of time these subjects remain free from MAC infection. The secondary objectives are to determine if the profile of host immune cells and cytokine responses in the blood (TH1 and TH2) predict risk of recurrent MAC disease in subjects who are withdrawn from anti-mycobacterial therapy and remain free from disease with subjects who are withdrawn from therapy and have recurrence of disease. In vitro responses to three different MAC antigens will be compared to determine which, if any, are best predictive of low vs. high risk of MAC disease in this population. Delayed type hypersensitivity skin test responses will be determined to see if they can be used to predict risk for MAC infection after discontinuation of anti-mycobacterial therapy. The study will also determine if frozen PBMC's can be used in lyphocyte proliferation assays as predictors of clinical outcome.